package com.mlh.stack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/6/19 16:34
 * @DESCRIPTION
 */
//给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
// 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
//输入: nums = [1,2,1]
// 输出: [2,-1,2]
// 解释: 第一个 1 的下一个更大的数是 2；
// 数字 2 找不到下一个更大的数；
// 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
public class 下一个更大元素2 {
    public int[] method1(int[] nums) {
        //循环遍历，循环到什么时候结束呢？
        //对一个具体的数来说循环到自己前一个数字才是循环了一圈，也是循环的结束
        //因此循环到数组最后一个数的前一位整个循环就结束了  0...end..0....end-1
        int[]res=new int[nums.length];
        Arrays.fill(res,-1);
        Deque<Integer>stack=new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                res[stack.peek()]=nums[i];
                stack.pop();
            }
            stack.push(i);
        }
        //此时数组已经遍历了一遍，stack中只剩下真正的右边没有更大数的数了
        //此时在遍历一次数组，这次就不需要将数字入栈了
        //因为此时只需要找到栈中数字右边（循环）的更大数，其他的数都已经找到了
        for (int i = 0; i < nums.length-1; i++) {
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                res[stack.peek()]=nums[i];
                stack.pop();
            }
        }
        return res;
    }
}
